/**
 * The MIT License (MIT)
 *
 * Copyright (c) 2013 Armin Lunkeit, Fabian Poehland, Leonard Scharff
 *
 * Permission is hereby granted, free of charge, to any person obtaining _a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
*/

package tub.adm1;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 
 * @author alunkeit
 *
 * This is a version of GoldbergTarjan.
 */
public class GoldbergTarjan 
{
  /**
   * Private array containing the flow values
   */
  private float[][] _flow;
  
  /**
   * Number of vertices in the graph
   */
  private int _vertexCnt;
  
  /**
   * Used for labeling
   */
  private int[] _labels;
  
  /**
   * Excess of a node
   */
  private float[] _excess;
  
  /**
   * Visiting counter of edges
   */
  private int[] _visited;
  
  /**
   * The underlying graph representation
   */
  private Graph _network;
  
  private HashMap<Integer, Integer> _mapping = new HashMap<Integer, Integer>();
  
  /**
   * Required for numeric stability. Comparing flow values > 0 leads to very long
   * iterations over the network.
   */
  private float _epsilon = 1/100000f;
  
  /**
   * Set this element to true to enable debug output.
   */
  private boolean _output = false;
  
  public GoldbergTarjan( Graph G )
  {
    
    this._network = G;
        
    init();
  }
  
  private void output( String out )
  {
    if( true == _output )
      System.out.println( out );
  }

  /**
   * Starts solving the problem
   * 
   * @param s The node to start from
   * @param t The targt node
   * @return A float value with the computed flow.
   */
  public float solve( int s, int t )
  {
    int start = _mapping.get( s );
    int end = _mapping.get( t );
    
    _labels[start] = _vertexCnt;
    _excess[start] = Integer.MAX_VALUE;
    
    List<Edge> edges = this._network.getEdges( s );
    
    for( Edge edge : edges )
    {
      if( (int) edge._headId == s )
      {
        int u = _mapping.get( edge._tailId );
        
        push( start, u );
      }
    }
    
    List<Integer> activeNodes = getActiveNodes( start, end );
    
    do
    {
      for( Integer i : activeNodes )
      {
        iterate( i );
      }
      
      activeNodes = getActiveNodes( start, end );
    
    } while( activeNodes.size() > 0 );

    Float flowValue = 0f;
    
    for( int i = 0; i < _vertexCnt; i++ )
    {
      flowValue += _flow[start][i];
    }
    
    return flowValue;
  }

  /**
   * Returns the list of active nodes between s and t
   * @param s - The start node
   * @param t - The target node
   * @return List of Integer values. The list might be empty.
   */
  private List<Integer> getActiveNodes( int s, int t )
  {
    LinkedList<Integer> result = new LinkedList<Integer>();
    
    for( int i = 0; i < _vertexCnt; i++ )
    {
      if( (i != s) & (i != t) )
      {
        if( _excess[i] > _epsilon )
        {
          result.add( (Integer) i );
        }
      }
    }
    return result;
  }

  /**
   * Iteration operation
   * 
   * @param v
   */
  private void iterate( int v )
  {
    Vertex vertex = _network.getVertices().get( v );
    
    List<Edge> edges = _network.getEdges( vertex._id );
    
    if( _excess[ v ] < _epsilon )
    {
      output( "..." );
      return;
    }
    else
    {
      output( "excess[" + v + "] := " + _excess[ v ] );
    }
      
    
    while( _excess[v] > _epsilon )
    {
      if( _visited[v] < edges.size() )
      {
        Edge e = edges.get( _visited[v] );
        
        if( (int) e._headId == (int) vertex._id )
        {
          int w = _mapping.get((int) e._tailId);
          
          float uf = e._weight - _flow[v][w];
          
          if( (uf > _epsilon ) & (_labels[v] == _labels[w] + 1) )
          {
            push( v, w, uf );
          }
          else
          {
            _visited[v] += 1;
          }
        }
        if( (int) e._tailId == (int) vertex._id )
        {
          if( !_network.isEdge( vertex._id, e._headId ) )
          {
            int w = _mapping.get((int) e._headId );
            
            float uf = _flow[w][v];
            
            if( (uf > _epsilon ) & (_labels[v] == _labels[w] + 1) )
            {
              push( v, w, uf );
            }
            else
            {
              _visited[v] += 1;
            }
          }
          else
          {
            _visited[v] += 1;
          }
        }
      }
      else
      {
        relabel( v );
        _visited[v] = 0;
      }
    }
  }

  /**
   * Relabel operation.
   * 
   * @param v
   */
  private void relabel( int v )
  {
    output( "relabel := " + v );
    
    Vertex  vertex      = _network.getVertices().get( v );
    List<Edge> edges    = this._network.getEdges( vertex._id );
    
    int w               = 0;
    float uf            = 0;
    int minHeight       = Integer.MAX_VALUE;
    
    for( Edge e : edges )
    {
      if( (int) e._headId == (int) vertex._id )
      {
        w = _mapping.get((int) e._tailId );
        
        uf = e._weight - _flow[v][w];
      }
      else if( (int) e._tailId == (int) vertex._id )
      {
        w = _mapping.get((int) e._headId );
        uf = _flow[w][v];
      }
      
      if( uf > _epsilon )
      {
        minHeight = Math.min( minHeight, _labels[w] );
      }
    }
    
    _labels[v] = minHeight + 1;
    output( "height[" + v + "] := " + v );
  }

  /**
   * Push operation used during initialization phase.
   * 
   * @param v
   * @param u
   */
  private void push( int v, int u )
  {
    List<Vertex> l = _network.getVertices();
    
    Edge e = _network.getEdge( l.get( v )._id, l.get( u )._id );
    
    float val = Math.min( _excess[v], e._weight - _flow[v][u] );
    _flow[v][u] += val;
    _flow[u][v] -= val;
    _excess[v]  -= val;
    _excess[u]  += val;
  }

  /**
   * Push operation used during iteration phase.
   * 
   * @param v
   * @param u
   * @param uf
   */
  private void push( int v, int u, float uf )
  {
    float val = Math.min( _excess[v], uf );
    
    output( "push v := " + v + " u := " + u + " val := " + val );
    
    if( val < _epsilon )
    {
      _flow[v][u] += val;
      _flow[u][v] -= val;
      _excess[v]  = 0;
      _excess[u]  += val;
      output( "small value condition reached!" );
      return;
    }
    
    _flow[v][u] += val;
    _flow[u][v] -= val;
    _excess[v]  -= val;
    _excess[u]  += val;
    
    output(  "pushing flow from v := " + v + " to u := " + u + " flow :=" + val );
  }
  
  
  /**
   * Initialization routine.
   * 
   */
  private void init()
  {
    // Initialize
    _vertexCnt  = _network.getVertices().size();
    _labels     = new int[_vertexCnt];
    _excess     = new float[_vertexCnt];
    _visited       = new int[_vertexCnt];
    _flow       = new float[_vertexCnt][_vertexCnt];
    
    List<Vertex> l = _network.getVertices();
    
    for( int i = 0; i < l.size(); i++ )
    {
      Vertex vertex = l.get( i );
     
      _mapping.put( vertex._id, i );
    }
  }
  
  //-------------------------------------------------------------
  // Inner classes required for implementation
  //-------------------------------------------------------------
  public static class Vertex
  {
    public Integer _id;
    
    public Integer _predecessor;
    
    public Integer _distance = 0;
    
    public float _excess;
  }
  
  public static class Edge 
  {
      public Integer _headId;
      public Integer _tailId;
      
      public float _weight;
      
      // used in EK implementation
      public float _rij;
      public float _fe;
      
      // used in gt implementation
      public float _f; // flow value
      public float _rf; // residual capacity
  }
}
